package 题目集.栈.计算器;

import java.util.*;

//https://vjudge.net.cn/contest/612014#problem/A
public class 加减乘 {
    public static void main(String[] args) {
        System.out.println(dfs(8));
//		for (int i = 0; i < nums.size(); i++) {
//			int[] num = nums.get(i);
//			char[] symbol = chars.get(i);
//
//			System.out.println(Arrays.toString(num));
//			System.out.println(Arrays.toString(symbol));
//			Syste.m.out.println("====================================");
//		}
//        set.forEach(System.out::println);
    }

    static int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    static char[] symbol = new char[9];
    //	static char[] symbol={'+','-','*','-','*','-','*','-','*'};
//	static {
//		System.out.println(handler());
//	}
    static List<int[]> nums = new ArrayList<>();
    static List<char[]> chars = new ArrayList<>();
    /**
     *
     */
    public static int dfs(int i) {
        int res = 0;
        if (i == 0) {
            symbol[i] = '+';
            if (handler()) {
                res++;
            }
            symbol[i] = '-';
            if (handler()) {
                res++;
            }
            symbol[i] = '*';
            if (handler()) {
                res++;
            }
            return res;
        }
        symbol[i] = '+';
        res += dfs(i - 1);
        symbol[i] = '-';
        res += dfs(i - 1);
        symbol[i] = '*';
        res += dfs(i - 1);
        return res;
    }

    static Map<Character, Integer> map = new HashMap<>();

    static {
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
    }

    public static boolean handler(){
        Stack<Integer> numberStack=new Stack<>();
        Stack<Character> symbolStack=new Stack<>();
        int i=0,j=0;
        numberStack.push(a[i++]);
        numberStack.push(a[i++]);
        symbolStack.push(symbol[j++]);
        while (i<a.length&&j<symbol.length){
            while (!symbolStack.isEmpty()&&map.get(symbol[j])<=map.get(symbolStack.peek())){    //如果之前的符号优先级高，则先计算之前的
                Integer right = numberStack.pop();
                Integer left = numberStack.pop();
                int res=calculate(left,right,symbolStack.pop());
                numberStack.push(res);
            }
            numberStack.push(a[i++]);
            symbolStack.push(symbol[j++]);
        }
        while (!symbolStack.isEmpty()){
            int res=calculate(numberStack.pop(),numberStack.pop(),symbolStack.pop());
            numberStack.push(res);
        }
        return numberStack.pop()==0;
    }

    public static int calculate(int l, int r, char s) {
        switch (s) {
            case '*':
                return l * r;
            case '-':
                return l - r;
            case '+':
                return l + r;
        }
        return 0;
    }
}
